<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<html>
	<head>
		<title>Sort Template</title>
<link href="../docs-assets/Breadcrumbs.css" rel="stylesheet" rev="stylesheet" type="text/css">
		<meta name="viewport" content="width=device-width initial-scale=1">
		<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
		<meta http-equiv="Content-Language" content="en-gb">

<link href="../docs-assets/Contents.css" rel="stylesheet" rev="stylesheet" type="text/css">
<link href="../docs-assets/Progress.css" rel="stylesheet" rev="stylesheet" type="text/css">
<link href="../docs-assets/Navigation.css" rel="stylesheet" rev="stylesheet" type="text/css">
<link href="../docs-assets/Fonts.css" rel="stylesheet" rev="stylesheet" type="text/css">
<link href="../docs-assets/Base.css" rel="stylesheet" rev="stylesheet" type="text/css">
<script>
MathJax = {
	tex: {
		inlineMath: '$', '$'], ['\\(', '\\)'
	},
	svg: {
		fontCache: 'global'
	}
};
</script>
<script type="text/javascript" id="MathJax-script" async
	src="https://cdn.jsdelivr.net/npm/mathjax@3/es5/tex-svg.js">
</script>

<link href="../docs-assets/Colours.css" rel="stylesheet" rev="stylesheet" type="text/css">
		
	</head>
	<body class="commentary-font">
		<nav role="navigation">
		<h1><a href="../index.html"><img src="../docs-assets/Inform.png" height=72> </a></h1>
<ul><li><a href="../index.html">home</a></li>
</ul><h2>Compiler</h2><ul>
<li><a href="../structure.html">structure</a></li>
<li><a href="../inbuildn.html">inbuild</a></li>
<li><a href="../inform7n.html">inform7</a></li>
<li><a href="../intern.html">inter</a></li>
<li><a href="../services.html">services</a></li>
<li><a href="../secrets.html">secrets</a></li>
</ul><h2>Other Tools</h2><ul>
<li><a href="../inblorbn.html">inblorb</a></li>
<li><a href="../inform6.html">inform6</a></li>
<li><a href="../inpolicyn.html">inpolicy</a></li>
</ul><h2>Resources</h2><ul>
<li><a href="../extensions.html">extensions</a></li>
<li><a href="../kits.html">kits</a></li>
</ul><h2>Repository</h2><ul>
<li><a href="https://github.com/ganelson/inform"><img src="../docs-assets/github.png" height=0> github</a></li>
</ul><h2>Related Projects</h2><ul>
<li><a href="https://github.com/ganelson/inweb"><img src="../docs-assets/github.png" height=0> inweb</a></li>
<li><a href="https://github.com/ganelson/intest"><img src="../docs-assets/github.png" height=0> intest</a></li>
</ul>
		</nav>
		<main role="main">
		<!-- Weave of 'Sort Template' generated by inweb -->
<div class="breadcrumbs">
    <ul class="crumbs"><li><a href="../index.html">Home</a></li><li><a href="../extensions.html">Kits</a></li><li><a href="index.html">BasicInformKit</a></li><li><b>Sort Template</b></li></ul></div>
<p class="purpose">To sort arrays.</p>

<ul class="toc"><li><a href="srtm.html#SP1">&#167;1. Storage</a></li><li><a href="srtm.html#SP2">&#167;2. Front End</a></li><li><a href="srtm.html#SP3">&#167;3. Sort Range</a></li><li><a href="srtm.html#SP4">&#167;4. Comparison and Exchange</a></li><li><a href="srtm.html#SP5">&#167;5. 4W37 Sort</a></li><li><a href="srtm.html#SP6">&#167;6. Insertion Sort</a></li><li><a href="srtm.html#SP7">&#167;7. In-Place Mergesort</a></li></ul><hr class="tocbar">

<p class="commentary firstcommentary"><a id="SP1" class="paragraph-anchor"></a><b>&#167;1. Storage.</b>We are required to use a stable sorting algorithm with very low, ideally zero,
auxiliary storage requirement. Exchanges are generally slower than comparisons
for the typical application (sorting tables, where entire rows must be
exchanged whereas only entries in a single column need be compared).
</p>

<p class="commentary">In fact, we store some details in global variables for convenience and to
avoid filling the stack with copies, but otherwise we will hardly need any
auxiliary storage.
</p>

<pre class="displayed-code all-displayed-code code-font">
<span class="reserved-syntax">Constant</span><span class="plain-syntax"> </span><span class="identifier-syntax">SORT_ASCENDING</span><span class="plain-syntax"> = </span><span class="constant-syntax">1</span><span class="plain-syntax">;</span>
<span class="reserved-syntax">Constant</span><span class="plain-syntax"> </span><span class="identifier-syntax">SORT_DESCENDING</span><span class="plain-syntax"> = -1;</span>

<span class="identifier-syntax">Global</span><span class="plain-syntax"> </span><span class="identifier-syntax">I7S_Tab</span><span class="plain-syntax">; </span><span class="comment-syntax">The array to be sorted, which can have almost any format</span>
<span class="identifier-syntax">Global</span><span class="plain-syntax"> </span><span class="identifier-syntax">I7S_Col</span><span class="plain-syntax">; </span><span class="comment-syntax">The "column number" in the array, if any</span>
<span class="identifier-syntax">Global</span><span class="plain-syntax"> </span><span class="identifier-syntax">I7S_Dir</span><span class="plain-syntax">; </span><span class="comment-syntax">The direction of sorting: ascending (1) or descending (-1)</span>
<span class="identifier-syntax">Global</span><span class="plain-syntax"> </span><span class="identifier-syntax">I7S_Swap</span><span class="plain-syntax">; </span><span class="comment-syntax">The current routine for swapping two fields</span>
<span class="identifier-syntax">Global</span><span class="plain-syntax"> </span><span class="identifier-syntax">I7S_Comp</span><span class="plain-syntax">; </span><span class="comment-syntax">The current routine for comparing two fields</span>
</pre>
<p class="commentary firstcommentary"><a id="SP2" class="paragraph-anchor"></a><b>&#167;2. Front End.</b>To perform a sort, we first call <span class="extract"><span class="extract-syntax">SetSortDomain</span></span> to declare the swap and
compare functions to be used, and then call <span class="extract"><span class="extract-syntax">SortArray</span></span> actually to sort. (It
would be nice to combine these in a single call, but I6 allows a maximum of
7 call arguments for a routine, and that would make 8.) These are the only
two routines which should ever be called from outside of this template
segment.
</p>

<p class="commentary">The swap and compare functions are expected to take two arguments, which
are the field numbers of the fields being swapped or compared, where fields
are numbered from 1. Comparison is like <span class="extract"><span class="extract-syntax">strcmp</span></span>: it returns 0 on equality,
and then is positive or negative according to which of the fields is
greater in value.
</p>

<pre class="displayed-code all-displayed-code code-font">
<span class="plain-syntax">[ </span><span class="identifier-syntax">SetSortDomain</span><span class="plain-syntax"> </span><span class="identifier-syntax">swapf</span><span class="plain-syntax"> </span><span class="identifier-syntax">compf</span><span class="plain-syntax">;</span>
<span class="plain-syntax">    </span><span class="identifier-syntax">I7S_Swap</span><span class="plain-syntax"> = </span><span class="identifier-syntax">swapf</span><span class="plain-syntax">;</span>
<span class="plain-syntax">    </span><span class="identifier-syntax">I7S_Comp</span><span class="plain-syntax"> = </span><span class="identifier-syntax">compf</span><span class="plain-syntax">;</span>
<span class="plain-syntax">];</span>

<span class="plain-syntax">[ </span><span class="identifier-syntax">SortArray</span><span class="plain-syntax"> </span><span class="identifier-syntax">tab</span><span class="plain-syntax"> </span><span class="identifier-syntax">col</span><span class="plain-syntax"> </span><span class="identifier-syntax">dir</span><span class="plain-syntax"> </span><span class="identifier-syntax">size</span><span class="plain-syntax"> </span><span class="identifier-syntax">algorithm</span><span class="plain-syntax">;</span>
<span class="plain-syntax">    </span><span class="identifier-syntax">I7S_Tab</span><span class="plain-syntax"> = </span><span class="identifier-syntax">tab</span><span class="plain-syntax">;</span>
<span class="plain-syntax">    </span><span class="identifier-syntax">I7S_Col</span><span class="plain-syntax"> = </span><span class="identifier-syntax">col</span><span class="plain-syntax">;</span>
<span class="plain-syntax">    </span><span class="identifier-syntax">I7S_Dir</span><span class="plain-syntax"> = </span><span class="identifier-syntax">dir</span><span class="plain-syntax">;</span>
<span class="plain-syntax">    </span><span class="identifier-syntax">SortRange</span><span class="plain-syntax">(0, </span><span class="identifier-syntax">size</span><span class="plain-syntax">, </span><span class="identifier-syntax">algorithm</span><span class="plain-syntax">);</span>
<span class="plain-syntax">];</span>
</pre>
<p class="commentary firstcommentary"><a id="SP3" class="paragraph-anchor"></a><b>&#167;3. Sort Range.</b>This routine sorts a range of fields \(x\leq i &lt; y\) within the array. Fields
are numbered from 0. The supplied <span class="extract"><span class="extract-syntax">algorithm</span></span> is an I6 routine to implement
a particular sorting algorithm; if it is not supplied, then in-place merge
sort is used by default.
</p>

<pre class="displayed-code all-displayed-code code-font">
<span class="plain-syntax">[ </span><span class="identifier-syntax">SortRange</span><span class="plain-syntax"> </span><span class="identifier-syntax">x</span><span class="plain-syntax"> </span><span class="identifier-syntax">y</span><span class="plain-syntax"> </span><span class="identifier-syntax">algorithm</span><span class="plain-syntax">;</span>
<span class="plain-syntax">    </span><span class="reserved-syntax">if</span><span class="plain-syntax"> (</span><span class="identifier-syntax">y</span><span class="plain-syntax"> - </span><span class="identifier-syntax">x</span><span class="plain-syntax"> &lt; </span><span class="constant-syntax">2</span><span class="plain-syntax">) </span><span class="reserved-syntax">return</span><span class="plain-syntax">;</span>
<span class="plain-syntax">    </span><span class="reserved-syntax">if</span><span class="plain-syntax"> (</span><span class="identifier-syntax">algorithm</span><span class="plain-syntax">) {</span>
<span class="plain-syntax">        (</span><span class="identifier-syntax">algorithm</span><span class="plain-syntax">)(</span><span class="identifier-syntax">x</span><span class="plain-syntax">, </span><span class="identifier-syntax">y</span><span class="plain-syntax">);</span>
<span class="plain-syntax">    } </span><span class="reserved-syntax">else</span><span class="plain-syntax"> {</span>
<span class="plain-syntax">        </span><span class="identifier-syntax">InPlaceMergeSortAlgorithm</span><span class="plain-syntax">(</span><span class="identifier-syntax">x</span><span class="plain-syntax">, </span><span class="identifier-syntax">y</span><span class="plain-syntax">);</span>
<span class="plain-syntax">    }</span>
<span class="plain-syntax">];</span>
</pre>
<p class="commentary firstcommentary"><a id="SP4" class="paragraph-anchor"></a><b>&#167;4. Comparison and Exchange.</b>These are instrumented versions of how to swap and compare fields; note that
the swap and compare functions are expected to number the fields from 1, not
from 0. (This is convenient both for tables and lists, where rows and entries
respectively are both numbered from 1.) The only access which the sorting
algorithms have to the actual data being sorted is through these routines.
</p>

<pre class="displayed-code all-displayed-code code-font">
<span class="plain-syntax">[ </span><span class="identifier-syntax">CompareFields</span><span class="plain-syntax"> </span><span class="identifier-syntax">x</span><span class="plain-syntax"> </span><span class="identifier-syntax">y</span><span class="plain-syntax">;</span>
<span class="plain-syntax">    </span><span class="reserved-syntax">return</span><span class="plain-syntax"> </span><span class="identifier-syntax">I7S_Dir</span><span class="plain-syntax">*</span><span class="identifier-syntax">I7S_Comp</span><span class="plain-syntax">(</span><span class="identifier-syntax">I7S_Tab</span><span class="plain-syntax">, </span><span class="identifier-syntax">I7S_Col</span><span class="plain-syntax">, </span><span class="identifier-syntax">x</span><span class="plain-syntax">+1, </span><span class="identifier-syntax">y</span><span class="plain-syntax">+1, </span><span class="identifier-syntax">I7S_Dir</span><span class="plain-syntax">);</span>
<span class="plain-syntax">];</span>

<span class="plain-syntax">[ </span><span class="identifier-syntax">ExchangeFields</span><span class="plain-syntax"> </span><span class="identifier-syntax">x</span><span class="plain-syntax"> </span><span class="identifier-syntax">y</span><span class="plain-syntax"> </span><span class="identifier-syntax">r</span><span class="plain-syntax">;</span>
<span class="plain-syntax">    </span><span class="identifier-syntax">r</span><span class="plain-syntax"> = </span><span class="identifier-syntax">I7S_Swap</span><span class="plain-syntax">(</span><span class="identifier-syntax">I7S_Tab</span><span class="plain-syntax">, </span><span class="identifier-syntax">x</span><span class="plain-syntax">+1, </span><span class="identifier-syntax">y</span><span class="plain-syntax">+1);</span>
<span class="plain-syntax">    </span><span class="reserved-syntax">return</span><span class="plain-syntax"> </span><span class="identifier-syntax">r</span><span class="plain-syntax">;</span>
<span class="plain-syntax">];</span>
</pre>
<p class="commentary firstcommentary"><a id="SP5" class="paragraph-anchor"></a><b>&#167;5. 4W37 Sort.</b>We now present three alternative sorting algorithms.
</p>

<p class="commentary">The first is the one used in builds up to and including 4W37: note that this is
not quite bubble sort, and that it is unstable. It is now no longer used, but
is so short that we might as well keep it in the code base in case anyone needs
to resurrect a very early I7 project.
</p>

<pre class="displayed-code all-displayed-code code-font">
<span class="plain-syntax">[ </span><span class="identifier-syntax">OldSortAlgorithm</span><span class="plain-syntax"> </span><span class="identifier-syntax">x</span><span class="plain-syntax"> </span><span class="identifier-syntax">y</span>
<span class="plain-syntax">    </span><span class="identifier-syntax">f</span><span class="plain-syntax"> </span><span class="identifier-syntax">i</span><span class="plain-syntax"> </span><span class="identifier-syntax">j</span><span class="plain-syntax">;</span>
<span class="plain-syntax">    </span><span class="reserved-syntax">if</span><span class="plain-syntax"> (</span><span class="identifier-syntax">y</span><span class="plain-syntax"> - </span><span class="identifier-syntax">x</span><span class="plain-syntax"> &lt; </span><span class="constant-syntax">2</span><span class="plain-syntax">) </span><span class="reserved-syntax">return</span><span class="plain-syntax">;</span>
<span class="plain-syntax">    </span><span class="identifier-syntax">f</span><span class="plain-syntax"> = </span><span class="reserved-syntax">true</span><span class="plain-syntax">;</span>
<span class="plain-syntax">    </span><span class="reserved-syntax">while</span><span class="plain-syntax"> (</span><span class="identifier-syntax">f</span><span class="plain-syntax">) {</span>
<span class="plain-syntax">        </span><span class="identifier-syntax">f</span><span class="plain-syntax"> = </span><span class="reserved-syntax">false</span><span class="plain-syntax">;</span>
<span class="plain-syntax">        </span><span class="reserved-syntax">for</span><span class="plain-syntax"> (</span><span class="identifier-syntax">i</span><span class="plain-syntax">=</span><span class="identifier-syntax">x</span><span class="plain-syntax">:</span><span class="identifier-syntax">i</span><span class="plain-syntax">&lt;</span><span class="identifier-syntax">y</span><span class="plain-syntax">:</span><span class="identifier-syntax">i</span><span class="plain-syntax">++)</span>
<span class="plain-syntax">            </span><span class="reserved-syntax">for</span><span class="plain-syntax"> (</span><span class="identifier-syntax">j</span><span class="plain-syntax">=</span><span class="identifier-syntax">i</span><span class="plain-syntax">+1:</span><span class="identifier-syntax">j</span><span class="plain-syntax">&lt;</span><span class="identifier-syntax">y</span><span class="plain-syntax">:</span><span class="identifier-syntax">j</span><span class="plain-syntax">++)</span>
<span class="plain-syntax">                </span><span class="reserved-syntax">if</span><span class="plain-syntax"> (</span><span class="identifier-syntax">CompareFields</span><span class="plain-syntax">(</span><span class="identifier-syntax">i</span><span class="plain-syntax">, </span><span class="identifier-syntax">j</span><span class="plain-syntax">) &gt; </span><span class="constant-syntax">0</span><span class="plain-syntax">) {</span>
<span class="plain-syntax">                    </span><span class="identifier-syntax">ExchangeFields</span><span class="plain-syntax">(</span><span class="identifier-syntax">i</span><span class="plain-syntax">, </span><span class="identifier-syntax">j</span><span class="plain-syntax">); </span><span class="identifier-syntax">f</span><span class="plain-syntax"> = </span><span class="reserved-syntax">true</span><span class="plain-syntax">; </span><span class="reserved-syntax">break</span><span class="plain-syntax">;</span>
<span class="plain-syntax">                }</span>
<span class="plain-syntax">    }</span>
<span class="plain-syntax">];</span>
</pre>
<p class="commentary firstcommentary"><a id="SP6" class="paragraph-anchor"></a><b>&#167;6. Insertion Sort.</b>A stable algorithm which has \(O(n^2)\) running time and therefore cannot be
used with large arrays, but which has good performance on nearly sorted tables,
and which has very low overhead.
</p>

<pre class="displayed-code all-displayed-code code-font">
<span class="plain-syntax">[ </span><span class="identifier-syntax">InsertionSortAlgorithm</span><span class="plain-syntax"> </span><span class="identifier-syntax">from</span><span class="plain-syntax"> </span><span class="reserved-syntax">to</span>
<span class="plain-syntax">    </span><span class="identifier-syntax">i</span><span class="plain-syntax"> </span><span class="identifier-syntax">j</span><span class="plain-syntax">;</span>
<span class="plain-syntax">    </span><span class="reserved-syntax">if</span><span class="plain-syntax"> (</span><span class="reserved-syntax">to</span><span class="plain-syntax"> &gt; </span><span class="identifier-syntax">from</span><span class="plain-syntax">+1) {</span>
<span class="plain-syntax">        </span><span class="reserved-syntax">for</span><span class="plain-syntax"> (</span><span class="identifier-syntax">i</span><span class="plain-syntax"> = </span><span class="identifier-syntax">from</span><span class="plain-syntax">+1: </span><span class="identifier-syntax">i</span><span class="plain-syntax"> &lt; </span><span class="reserved-syntax">to</span><span class="plain-syntax">: </span><span class="identifier-syntax">i</span><span class="plain-syntax">++) {</span>
<span class="plain-syntax">            </span><span class="reserved-syntax">for</span><span class="plain-syntax"> (</span><span class="identifier-syntax">j</span><span class="plain-syntax"> = </span><span class="identifier-syntax">i</span><span class="plain-syntax">: </span><span class="identifier-syntax">j</span><span class="plain-syntax"> &gt; </span><span class="identifier-syntax">from</span><span class="plain-syntax">: </span><span class="identifier-syntax">j</span><span class="plain-syntax">--) {</span>
<span class="plain-syntax">                </span><span class="reserved-syntax">if</span><span class="plain-syntax"> (</span><span class="identifier-syntax">CompareFields</span><span class="plain-syntax">(</span><span class="identifier-syntax">j</span><span class="plain-syntax">, </span><span class="identifier-syntax">j</span><span class="plain-syntax">-1) &lt; </span><span class="constant-syntax">0</span><span class="plain-syntax">)</span>
<span class="plain-syntax">                    </span><span class="identifier-syntax">ExchangeFields</span><span class="plain-syntax">(</span><span class="identifier-syntax">j</span><span class="plain-syntax">, </span><span class="identifier-syntax">j</span><span class="plain-syntax">-1);</span>
<span class="plain-syntax">                </span><span class="reserved-syntax">else</span><span class="plain-syntax"> </span><span class="reserved-syntax">break</span><span class="plain-syntax">;</span>
<span class="plain-syntax">            }</span>
<span class="plain-syntax">        }</span>
<span class="plain-syntax">    }</span>
<span class="plain-syntax">];</span>
</pre>
<p class="commentary firstcommentary"><a id="SP7" class="paragraph-anchor"></a><b>&#167;7. In-Place Mergesort.</b>A stable algorithm with \(O(n\log n)\) running time, at some stack cost, and
which is generally good for nearly sorted tables, but which is also complex
and has some overhead. The code here mostly follows Thomas Baudel's
implementation, which in turn follows the <span class="extract"><span class="extract-syntax">C++</span></span> STL library.
</p>

<pre class="displayed-code all-displayed-code code-font">
<span class="plain-syntax">[ </span><span class="identifier-syntax">InPlaceMergeSortAlgorithm</span><span class="plain-syntax"> </span><span class="identifier-syntax">from</span><span class="plain-syntax"> </span><span class="reserved-syntax">to</span>
<span class="plain-syntax">    </span><span class="identifier-syntax">middle</span><span class="plain-syntax">;</span>
<span class="plain-syntax">    </span><span class="reserved-syntax">if</span><span class="plain-syntax"> (</span><span class="reserved-syntax">to</span><span class="plain-syntax"> - </span><span class="identifier-syntax">from</span><span class="plain-syntax"> &lt; </span><span class="constant-syntax">12</span><span class="plain-syntax">) {</span>
<span class="plain-syntax">        </span><span class="reserved-syntax">if</span><span class="plain-syntax"> (</span><span class="reserved-syntax">to</span><span class="plain-syntax"> - </span><span class="identifier-syntax">from</span><span class="plain-syntax"> &lt; </span><span class="constant-syntax">2</span><span class="plain-syntax">) </span><span class="reserved-syntax">return</span><span class="plain-syntax">;</span>
<span class="plain-syntax">        </span><span class="identifier-syntax">InsertionSortAlgorithm</span><span class="plain-syntax">(</span><span class="identifier-syntax">from</span><span class="plain-syntax">, </span><span class="reserved-syntax">to</span><span class="plain-syntax">);</span>
<span class="plain-syntax">        </span><span class="reserved-syntax">return</span><span class="plain-syntax">;</span>
<span class="plain-syntax">    }</span>
<span class="plain-syntax">    </span><span class="identifier-syntax">middle</span><span class="plain-syntax"> = (</span><span class="identifier-syntax">from</span><span class="plain-syntax"> + </span><span class="reserved-syntax">to</span><span class="plain-syntax">)/2;</span>
<span class="plain-syntax">    </span><span class="identifier-syntax">InPlaceMergeSortAlgorithm</span><span class="plain-syntax">(</span><span class="identifier-syntax">from</span><span class="plain-syntax">, </span><span class="identifier-syntax">middle</span><span class="plain-syntax">);</span>
<span class="plain-syntax">    </span><span class="identifier-syntax">InPlaceMergeSortAlgorithm</span><span class="plain-syntax">(</span><span class="identifier-syntax">middle</span><span class="plain-syntax">, </span><span class="reserved-syntax">to</span><span class="plain-syntax">);</span>
<span class="plain-syntax">    </span><span class="identifier-syntax">IPMS_Merge</span><span class="plain-syntax">(</span><span class="identifier-syntax">from</span><span class="plain-syntax">, </span><span class="identifier-syntax">middle</span><span class="plain-syntax">, </span><span class="reserved-syntax">to</span><span class="plain-syntax">, </span><span class="identifier-syntax">middle</span><span class="plain-syntax">-</span><span class="identifier-syntax">from</span><span class="plain-syntax">, </span><span class="reserved-syntax">to</span><span class="plain-syntax"> - </span><span class="identifier-syntax">middle</span><span class="plain-syntax">);</span>
<span class="plain-syntax">];</span>

<span class="plain-syntax">[ </span><span class="identifier-syntax">IPMS_Lower</span><span class="plain-syntax"> </span><span class="identifier-syntax">from</span><span class="plain-syntax"> </span><span class="reserved-syntax">to</span><span class="plain-syntax"> </span><span class="identifier-syntax">val</span>
<span class="plain-syntax">    </span><span class="identifier-syntax">len</span><span class="plain-syntax"> </span><span class="identifier-syntax">half</span><span class="plain-syntax"> </span><span class="identifier-syntax">mid</span><span class="plain-syntax">;</span>
<span class="plain-syntax">    </span><span class="identifier-syntax">len</span><span class="plain-syntax"> = </span><span class="reserved-syntax">to</span><span class="plain-syntax"> - </span><span class="identifier-syntax">from</span><span class="plain-syntax">;</span>
<span class="plain-syntax">    </span><span class="reserved-syntax">while</span><span class="plain-syntax"> (</span><span class="identifier-syntax">len</span><span class="plain-syntax"> &gt; </span><span class="constant-syntax">0</span><span class="plain-syntax">) {</span>
<span class="plain-syntax">        </span><span class="identifier-syntax">half</span><span class="plain-syntax"> = </span><span class="identifier-syntax">len</span><span class="plain-syntax">/2;</span>
<span class="plain-syntax">        </span><span class="identifier-syntax">mid</span><span class="plain-syntax"> = </span><span class="identifier-syntax">from</span><span class="plain-syntax"> + </span><span class="identifier-syntax">half</span><span class="plain-syntax">;</span>
<span class="plain-syntax">        </span><span class="reserved-syntax">if</span><span class="plain-syntax"> (</span><span class="identifier-syntax">CompareFields</span><span class="plain-syntax">(</span><span class="identifier-syntax">mid</span><span class="plain-syntax">, </span><span class="identifier-syntax">val</span><span class="plain-syntax">) &lt; </span><span class="constant-syntax">0</span><span class="plain-syntax">) {</span>
<span class="plain-syntax">            </span><span class="identifier-syntax">from</span><span class="plain-syntax"> = </span><span class="identifier-syntax">mid</span><span class="plain-syntax"> + </span><span class="constant-syntax">1</span><span class="plain-syntax">;</span>
<span class="plain-syntax">            </span><span class="identifier-syntax">len</span><span class="plain-syntax"> = </span><span class="identifier-syntax">len</span><span class="plain-syntax"> - </span><span class="identifier-syntax">half</span><span class="plain-syntax"> -1;</span>
<span class="plain-syntax">        } </span><span class="reserved-syntax">else</span><span class="plain-syntax"> </span><span class="identifier-syntax">len</span><span class="plain-syntax"> = </span><span class="identifier-syntax">half</span><span class="plain-syntax">;</span>
<span class="plain-syntax">    }</span>
<span class="plain-syntax">    </span><span class="reserved-syntax">return</span><span class="plain-syntax"> </span><span class="identifier-syntax">from</span><span class="plain-syntax">;</span>
<span class="plain-syntax">];</span>

<span class="plain-syntax">[ </span><span class="identifier-syntax">IPMS_Upper</span><span class="plain-syntax"> </span><span class="identifier-syntax">from</span><span class="plain-syntax"> </span><span class="reserved-syntax">to</span><span class="plain-syntax"> </span><span class="identifier-syntax">val</span>
<span class="plain-syntax">    </span><span class="identifier-syntax">len</span><span class="plain-syntax"> </span><span class="identifier-syntax">half</span><span class="plain-syntax"> </span><span class="identifier-syntax">mid</span><span class="plain-syntax">;</span>
<span class="plain-syntax">    </span><span class="identifier-syntax">len</span><span class="plain-syntax"> = </span><span class="reserved-syntax">to</span><span class="plain-syntax"> - </span><span class="identifier-syntax">from</span><span class="plain-syntax">;</span>
<span class="plain-syntax">    </span><span class="reserved-syntax">while</span><span class="plain-syntax"> (</span><span class="identifier-syntax">len</span><span class="plain-syntax"> &gt; </span><span class="constant-syntax">0</span><span class="plain-syntax">) {</span>
<span class="plain-syntax">        </span><span class="identifier-syntax">half</span><span class="plain-syntax"> = </span><span class="identifier-syntax">len</span><span class="plain-syntax">/2;</span>
<span class="plain-syntax">        </span><span class="identifier-syntax">mid</span><span class="plain-syntax"> = </span><span class="identifier-syntax">from</span><span class="plain-syntax"> + </span><span class="identifier-syntax">half</span><span class="plain-syntax">;</span>
<span class="plain-syntax">        </span><span class="reserved-syntax">if</span><span class="plain-syntax"> (</span><span class="identifier-syntax">CompareFields</span><span class="plain-syntax">(</span><span class="identifier-syntax">val</span><span class="plain-syntax">, </span><span class="identifier-syntax">mid</span><span class="plain-syntax">) &lt; </span><span class="constant-syntax">0</span><span class="plain-syntax">)</span>
<span class="plain-syntax">            </span><span class="identifier-syntax">len</span><span class="plain-syntax"> = </span><span class="identifier-syntax">half</span><span class="plain-syntax">;</span>
<span class="plain-syntax">        </span><span class="reserved-syntax">else</span><span class="plain-syntax"> {</span>
<span class="plain-syntax">            </span><span class="identifier-syntax">from</span><span class="plain-syntax"> = </span><span class="identifier-syntax">mid</span><span class="plain-syntax"> + </span><span class="constant-syntax">1</span><span class="plain-syntax">;</span>
<span class="plain-syntax">            </span><span class="identifier-syntax">len</span><span class="plain-syntax"> = </span><span class="identifier-syntax">len</span><span class="plain-syntax"> - </span><span class="identifier-syntax">half</span><span class="plain-syntax"> -1;</span>
<span class="plain-syntax">        }</span>
<span class="plain-syntax">    }</span>
<span class="plain-syntax">    </span><span class="reserved-syntax">return</span><span class="plain-syntax"> </span><span class="identifier-syntax">from</span><span class="plain-syntax">;</span>
<span class="plain-syntax">];</span>

<span class="plain-syntax">[ </span><span class="identifier-syntax">IPMS_Reverse</span><span class="plain-syntax"> </span><span class="identifier-syntax">from</span><span class="plain-syntax"> </span><span class="reserved-syntax">to</span><span class="plain-syntax">;</span>
<span class="plain-syntax">    </span><span class="reserved-syntax">while</span><span class="plain-syntax"> (</span><span class="identifier-syntax">from</span><span class="plain-syntax"> &lt; </span><span class="reserved-syntax">to</span><span class="plain-syntax">) {</span>
<span class="plain-syntax">        </span><span class="identifier-syntax">ExchangeFields</span><span class="plain-syntax">(</span><span class="identifier-syntax">from</span><span class="plain-syntax">++, </span><span class="reserved-syntax">to</span><span class="plain-syntax">--);</span>
<span class="plain-syntax">    }</span>
<span class="plain-syntax">];</span>

<span class="plain-syntax">[ </span><span class="identifier-syntax">IPMS_Rotate</span><span class="plain-syntax"> </span><span class="identifier-syntax">from</span><span class="plain-syntax"> </span><span class="identifier-syntax">mid</span><span class="plain-syntax"> </span><span class="reserved-syntax">to</span>
<span class="plain-syntax">    </span><span class="identifier-syntax">n</span><span class="plain-syntax"> </span><span class="identifier-syntax">val</span><span class="plain-syntax"> </span><span class="identifier-syntax">shift</span><span class="plain-syntax"> </span><span class="identifier-syntax">p1</span><span class="plain-syntax"> </span><span class="identifier-syntax">p2</span><span class="plain-syntax">;</span>
<span class="plain-syntax">    </span><span class="reserved-syntax">if</span><span class="plain-syntax"> ((</span><span class="identifier-syntax">from</span><span class="plain-syntax">==</span><span class="identifier-syntax">mid</span><span class="plain-syntax">) || (</span><span class="identifier-syntax">mid</span><span class="plain-syntax">==</span><span class="reserved-syntax">to</span><span class="plain-syntax">)) </span><span class="reserved-syntax">return</span><span class="plain-syntax">;</span>
<span class="plain-syntax">    </span><span class="identifier-syntax">IPMS_Reverse</span><span class="plain-syntax">(</span><span class="identifier-syntax">from</span><span class="plain-syntax">, </span><span class="identifier-syntax">mid</span><span class="plain-syntax">-1);</span>
<span class="plain-syntax">    </span><span class="identifier-syntax">IPMS_Reverse</span><span class="plain-syntax">(</span><span class="identifier-syntax">mid</span><span class="plain-syntax">, </span><span class="reserved-syntax">to</span><span class="plain-syntax">-1);</span>
<span class="plain-syntax">    </span><span class="identifier-syntax">IPMS_Reverse</span><span class="plain-syntax">(</span><span class="identifier-syntax">from</span><span class="plain-syntax">, </span><span class="reserved-syntax">to</span><span class="plain-syntax">-1);</span>
<span class="plain-syntax">];</span>

<span class="plain-syntax">[ </span><span class="identifier-syntax">IPMS_Merge</span><span class="plain-syntax"> </span><span class="identifier-syntax">from</span><span class="plain-syntax"> </span><span class="identifier-syntax">pivot</span><span class="plain-syntax"> </span><span class="reserved-syntax">to</span><span class="plain-syntax"> </span><span class="identifier-syntax">len1</span><span class="plain-syntax"> </span><span class="identifier-syntax">len2</span>
<span class="plain-syntax">    </span><span class="identifier-syntax">first_cut</span><span class="plain-syntax"> </span><span class="identifier-syntax">second_cut</span><span class="plain-syntax"> </span><span class="identifier-syntax">len11</span><span class="plain-syntax"> </span><span class="identifier-syntax">len22</span><span class="plain-syntax"> </span><span class="identifier-syntax">new_mid</span><span class="plain-syntax">;</span>
<span class="plain-syntax">    </span><span class="reserved-syntax">if</span><span class="plain-syntax"> ((</span><span class="identifier-syntax">len1</span><span class="plain-syntax"> == </span><span class="constant-syntax">0</span><span class="plain-syntax">) || (</span><span class="identifier-syntax">len2</span><span class="plain-syntax"> == </span><span class="constant-syntax">0</span><span class="plain-syntax">)) </span><span class="reserved-syntax">return</span><span class="plain-syntax">;</span>
<span class="plain-syntax">    </span><span class="reserved-syntax">if</span><span class="plain-syntax"> (</span><span class="identifier-syntax">len1</span><span class="plain-syntax">+</span><span class="identifier-syntax">len2</span><span class="plain-syntax"> == </span><span class="constant-syntax">2</span><span class="plain-syntax">) {</span>
<span class="plain-syntax">        </span><span class="reserved-syntax">if</span><span class="plain-syntax"> (</span><span class="identifier-syntax">CompareFields</span><span class="plain-syntax">(</span><span class="identifier-syntax">pivot</span><span class="plain-syntax">, </span><span class="identifier-syntax">from</span><span class="plain-syntax">) &lt; </span><span class="constant-syntax">0</span><span class="plain-syntax">)</span>
<span class="plain-syntax">        </span><span class="identifier-syntax">ExchangeFields</span><span class="plain-syntax">(</span><span class="identifier-syntax">pivot</span><span class="plain-syntax">, </span><span class="identifier-syntax">from</span><span class="plain-syntax">);</span>
<span class="plain-syntax">        </span><span class="reserved-syntax">return</span><span class="plain-syntax">;</span>
<span class="plain-syntax">    }</span>
<span class="plain-syntax">    </span><span class="reserved-syntax">if</span><span class="plain-syntax"> (</span><span class="identifier-syntax">len1</span><span class="plain-syntax"> &gt; </span><span class="identifier-syntax">len2</span><span class="plain-syntax">) {</span>
<span class="plain-syntax">        </span><span class="identifier-syntax">len11</span><span class="plain-syntax"> = </span><span class="identifier-syntax">len1</span><span class="plain-syntax">/2;</span>
<span class="plain-syntax">        </span><span class="identifier-syntax">first_cut</span><span class="plain-syntax"> = </span><span class="identifier-syntax">from</span><span class="plain-syntax"> + </span><span class="identifier-syntax">len11</span><span class="plain-syntax">;</span>
<span class="plain-syntax">        </span><span class="identifier-syntax">second_cut</span><span class="plain-syntax"> = </span><span class="identifier-syntax">IPMS_Lower</span><span class="plain-syntax">(</span><span class="identifier-syntax">pivot</span><span class="plain-syntax">, </span><span class="reserved-syntax">to</span><span class="plain-syntax">, </span><span class="identifier-syntax">first_cut</span><span class="plain-syntax">);</span>
<span class="plain-syntax">        </span><span class="identifier-syntax">len22</span><span class="plain-syntax"> = </span><span class="identifier-syntax">second_cut</span><span class="plain-syntax"> - </span><span class="identifier-syntax">pivot</span><span class="plain-syntax">;</span>
<span class="plain-syntax">    } </span><span class="reserved-syntax">else</span><span class="plain-syntax"> {</span>
<span class="plain-syntax">        </span><span class="identifier-syntax">len22</span><span class="plain-syntax"> = </span><span class="identifier-syntax">len2</span><span class="plain-syntax">/2;</span>
<span class="plain-syntax">        </span><span class="identifier-syntax">second_cut</span><span class="plain-syntax"> = </span><span class="identifier-syntax">pivot</span><span class="plain-syntax"> + </span><span class="identifier-syntax">len22</span><span class="plain-syntax">;</span>
<span class="plain-syntax">        </span><span class="identifier-syntax">first_cut</span><span class="plain-syntax"> = </span><span class="identifier-syntax">IPMS_Upper</span><span class="plain-syntax">(</span><span class="identifier-syntax">from</span><span class="plain-syntax">, </span><span class="identifier-syntax">pivot</span><span class="plain-syntax">, </span><span class="identifier-syntax">second_cut</span><span class="plain-syntax">);</span>
<span class="plain-syntax">        </span><span class="identifier-syntax">len11</span><span class="plain-syntax"> = </span><span class="identifier-syntax">first_cut</span><span class="plain-syntax"> - </span><span class="identifier-syntax">from</span><span class="plain-syntax">;</span>
<span class="plain-syntax">    }</span>
<span class="plain-syntax">    </span><span class="identifier-syntax">IPMS_Rotate</span><span class="plain-syntax">(</span><span class="identifier-syntax">first_cut</span><span class="plain-syntax">, </span><span class="identifier-syntax">pivot</span><span class="plain-syntax">, </span><span class="identifier-syntax">second_cut</span><span class="plain-syntax">);</span>
<span class="plain-syntax">    </span><span class="identifier-syntax">new_mid</span><span class="plain-syntax"> = </span><span class="identifier-syntax">first_cut</span><span class="plain-syntax"> + </span><span class="identifier-syntax">len22</span><span class="plain-syntax">;</span>
<span class="plain-syntax">    </span><span class="identifier-syntax">IPMS_Merge</span><span class="plain-syntax">(</span><span class="identifier-syntax">from</span><span class="plain-syntax">, </span><span class="identifier-syntax">first_cut</span><span class="plain-syntax">, </span><span class="identifier-syntax">new_mid</span><span class="plain-syntax">, </span><span class="identifier-syntax">len11</span><span class="plain-syntax">, </span><span class="identifier-syntax">len22</span><span class="plain-syntax">);</span>
<span class="plain-syntax">    </span><span class="identifier-syntax">IPMS_Merge</span><span class="plain-syntax">(</span><span class="identifier-syntax">new_mid</span><span class="plain-syntax">, </span><span class="identifier-syntax">second_cut</span><span class="plain-syntax">, </span><span class="reserved-syntax">to</span><span class="plain-syntax">, </span><span class="identifier-syntax">len1</span><span class="plain-syntax"> - </span><span class="identifier-syntax">len11</span><span class="plain-syntax">, </span><span class="identifier-syntax">len2</span><span class="plain-syntax"> - </span><span class="identifier-syntax">len22</span><span class="plain-syntax">);</span>
<span class="plain-syntax">];</span>
</pre>
<nav role="progress"><div class="progresscontainer">
    <ul class="progressbar"><li class="progressprev"><a href="mttm.html">&#10094;</a></li><li class="progresssection"><a href="dftm.html">dftm</a></li><li class="progresssection"><a href="sttm.html">sttm</a></li><li class="progresssection"><a href="uttm.html">uttm</a></li><li class="progresssection"><a href="prgrp.html">prgrp</a></li><li class="progresssection"><a href="mttm.html">mttm</a></li><li class="progresscurrent">srtm</li><li class="progresssection"><a href="tbtm.html">tbtm</a></li><li class="progresssection"><a href="mstck.html">mstck</a></li><li class="progresssection"><a href="rltm.html">rltm</a></li><li class="progresssection"><a href="actm.html">actm</a></li><li class="progresssection"><a href="prtm.html">prtm</a></li><li class="progresssection"><a href="flx.html">flx</a></li><li class="progresssection"><a href="blckv.html">blckv</a></li><li class="progresssection"><a href="kntm.html">kntm</a></li><li class="progresssection"><a href="txtm.html">txtm</a></li><li class="progresssection"><a href="chtm.html">chtm</a></li><li class="progresssection"><a href="rgtm.html">rgtm</a></li><li class="progresssection"><a href="lstm.html">lstm</a></li><li class="progresssection"><a href="cmtm.html">cmtm</a></li><li class="progresssection"><a href="rkt.html">rkt</a></li><li class="progresssection"><a href="rltns.html">rltns</a></li><li class="progresssection"><a href="prtm2.html">prtm2</a></li><li class="progresssection"><a href="rttm.html">rttm</a></li><li class="progressnext"><a href="tbtm.html">&#10095;</a></li></ul></div>
</nav><!-- End of weave -->

		</main>
	</body>
</html>

